A method of combining the HVQ compression and decompression of image pixels with ninety degree rotation so that both can be accomplished in less time, and using less hardware, than if both operations were done separately.
When data must be transmitted or stored it is usually compressed first, to reduce the transmission time or storage requirement. This is especially true of image data which can consist of four color separations of 8-bit pixels.
One method of compression is xe2x80x9chierarchical vector quantizationxe2x80x9d (HVQ), where a block of data can be reduced to a single codeword in a number of steps. This method is described in U.S. Pat. No. 5,602,589, and is incorporated by reference herein. This procedure can be explained most clearly by the use of a numerical example in connection with FIG. 1a of that patent. Assume that a 2 by 4 pixel block, 8 bits per pixel, is to be compressed to one 9-bit number. First, each pair of pixels is applied to a stage 1 look up table (LUT) containing 9-bit code words, each code word being associated with a two-pixel bit pattern. The table is set up so that if an exact match of the input pixel bits is not available, then a codeword associated with the closest match is output instead. The ultimate output of this stage 1 is four codewords, each describing the closest match to the bit pattern of the two input pixels. Since the exact match frequently is not possible, this compression is inherently lossy to some extent. The output of the first stage is four 9-bit codewords.
Assuming this amount of compression is not sufficient, these four codewords, each representing the bit pattern of a 1 by 2 pixel block are next applied to two stage 2 tables, resulting in a total of two 9-bit output codewords, each representing the bit pattern of a 2 by 2 pixel block. If the compression is still insufficient, these two are applied to the stage 3 table to yield the final output word, which is associated with a 2 by 4 pixel block. It can now be seen that this method is hierarchical in that a plurality of stages are used, it involves vectors since the input pixels have a directional relationship with each other, and is quantized in that a number of levels can be implemented to achieve any degree of compression.
For decompression, each codeword is simply applied to a 256K by 64 bit LUT which outputs the bit pattern of the entire 8-pixel block.
In the field of image rotation it is frequently necessary that an image scanned into the system in one orientation, such as protrait, must be printed in another orientation, such as landscape. Therefore, there is a need for ninety degree rotation hardware or software. One solution to this problem is to design a memory that can be loaded or read from vertically or horizontally. Then, to rotate the pixels in a block, the block is loaded into the memory one column at a time, and read out one row at a time. Of course, this requires additional circuitry or software, as well as additional operating time.
In a system which requires data compression as well as image rotation, the HVQ compression hardware can be modified to also produce image rotation at little added cost and operating time. To explain this by using a numerical example, assume an input set of eight pixels that is four high and two wide. This can be compressed into a single output code word. However, in the decoder, when this is applied to the look-up table, it would be just as simple to have there produced eight pixels that are arranged as two high by four wide to produce an image that is the rotated image of the input.